1984. Minimum Difference Between Highest and Lowest of K Scores

Easy

題目描述

Description

You are given a 0-indexed integer array nums, where nums[i] represents the score of the ith student. You are also given an integer k.

Pick the scores of any k students from the array so that the difference between the highest and the lowest of the k scores is minimized.

Return the minimum possible difference.

Example 1:

Input: nums = [90], k = 1
Output: 0
Explanation:
There is one way to pick score(s) of one student:
-[90]. The difference between the highest and lowest score is 90 - 90 = 0.
The minimum possible difference is 0.

Example 2:

Input: nums = [9,4,1,7], k = 2
Output: 2
Explanation:
There are six ways to pick score(s) of two students:

• [9,4,1,7]. The difference between the highest and lowest score is 9 - 4 = 5.
• [9,4,1,7]. The difference between the highest and lowest score is 9 - 1 = 8.
• [9,4,1,7]. The difference between the highest and lowest score is 9 - 7 = 2.
• [9,4,1,7]. The difference between the highest and lowest score is 4 - 1 = 3.
• [9,4,1,7]. The difference between the highest and lowest score is 7 - 4 = 3.
• [9,4,1,7]. The difference between the highest and lowest score is 7 - 1 = 6.
  The minimum possible difference is 2.

Constraints:

• 1 <= k <= nums.length <= 1000
• 0 <= nums[i] <= $10^5$

解答

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minimumDifference = function (nums, k) {
  nums.sort((a, b) => b - a);

  let left = 0;
  let right = k - 1;
  let minimumDifference = Infinity;

  while (right < nums.length) {
    const difference = nums[left] - nums[right];
    minimumDifference = Math.min(minimumDifference, difference);
    left++;
    right++;
  }

  return minimumDifference;
};

解題思路

根據題目的 hints 與 topics 得知要將題目給的 nums 排序後，使用 Sliding Window 的方式來解題，而 Sliding Window 的大小是由 k 來決定的。

var minimumDifference = function (nums, k) {
  nums.sort((a, b) => b - a); // 由大排到小，這樣子 left 就會大於 right

  let left = 0;
  let right = k - 1;
  let minimumDifference = Infinity; // 因為是找minimum所以初始值無限大

  while (right < nums.length) {
    // 當 sliding window 還沒結束時後就持續算 difference，並每次更新 minimumDifference
    const difference = nums[left] - nums[right];
    minimumDifference = Math.min(minimumDifference, difference);
    left++;
    right++; // 算完之後 sliding window 往右移動
  }

  return minimumDifference; // while迴圈結束後回傳結果
};

心得

一開始覺得看不太懂題目但竟然一次就過ㄌ耶！